"""
快速排序
先选第一个数，根据这个数，把列表数据拆分成两部分，左边比它小，右边比它大，再把这个数归位到中间
并把这个数的 新下标 返回

根据新下标，再对左右两边的区域，进行相同的操作
每个区域，先把第一个数归位，把该区域拆分成两部分，左边比它小，右边比它大，再把这个数归位到中间
并把这个数的 新下标 返回

循环往复，列表也就排好序了

假设每次找到的数，都恰好是中间的数
每一层的拆分归位，时间复杂度都是O(n)
              16
        8            8
    4      4      4     4
  2   2  2   2  2  2  2  2
  11 11 11  11 11 11 11 11
有多少层-----2的4次方=16
            所以log2的4次方=4
            即有logn层
因此，时间复杂度是 O(nlogn)

注意：
-----递归深度问题

-----最坏情况：列表是有序倒序的话，我们选取的如果是第一个数，那就是最大的数了
            每次只移动一个数
     解决办法-----随机选取

"""


def partition(li, low, high):
    tmp = li[low]
    while low < high:
        # 1、从右边找比tmp小的数
        while low < high and li[high] >= tmp:
            high -= 1
        # 找到了，把右边的值赋给左边
        li[low] = li[high]
        # 2、从左边找比tmp大的数
        while low < high and li[low] <= tmp:
            low += 1
        # 找到了，把左边的值赋给右边
        li[high] = li[low]
    li[low] = tmp
    return low


def quick_sort(li, low, high):
    if low < high:
        mid = partition(li, low, high)
        quick_sort(li, low, mid - 1)
        quick_sort(li, mid + 1, high)


if __name__ == '__main__':
    li = [5, 2, 4, 1, 3, 4, 6]
    quick_sort(li, 0, len(li) - 1)
    print(li)
